//顺序串基本运算的算法
#include <stdio.h>
#include <string.h>

#define MaxSize 20
typedef struct
{
	char data[MaxSize];
	int length;			//串长
} SqString;
void StrAssign(SqString& s, char cstr[])	//字符串常量赋给串s
{
	int i;
	for (i = 0; cstr[i] != '\0'; i++)
		s.data[i] = cstr[i];
	s.length = i;
}
void StrCopy(SqString& s, SqString t)	//串复制
{
	int i;
	for (i = 0; i < t.length; i++)
		s.data[i] = t.data[i];
	s.length = t.length;
}

void GetNextval(SqString t, int nextval[])  //由模式串t求出nextval值
{
	int j = 0, k = -1;
	nextval[0] = -1;
	while (j < t.length)
	{
		if (k == -1 || t.data[j] == t.data[k])
		{
			j++; k++;
			if (t.data[j] != t.data[k])
				nextval[j] = k;
			else
				nextval[j] = nextval[k];
		}
		else  k = nextval[k];
	}
}

int KMPIndex1(SqString s, SqString t)    //修正的KMP算法
{
	int nextval[MaxSize], i = 0, j = 0;
	GetNextval(t, nextval);
	while (i < s.length && j < t.length)
	{
		if (j == -1 || s.data[i] == t.data[j])
		{
			i++; j++;
		}
		else j = nextval[j];
	}
	if (j >= t.length)
		return(i - t.length);
	else
		return(-1);
}
SqString RepStr(SqString s, int i, int j, SqString t)	//子串替换
{
	int k;
	SqString str;
	str.length = 0;
	if (i <= 0 || i > s.length || i + j - 1 > s.length) //参数不正确时返回空串
		return str;
	for (k = 0; k < i - 1; k++)				//将s.data[0..i-2]复制到str
		str.data[k] = s.data[k];
	for (k = 0; k < t.length; k++)   		//将t.data[0..t.length-1]复制到str
		str.data[i + k - 1] = t.data[k];
	for (k = i + j - 1; k < s.length; k++)	//将s.data[i+j-1..s.length-1]复制到str
		str.data[t.length + k - j] = s.data[k];
	str.length = s.length - j + t.length;
	return str;
}
SqString SubStr(SqString s, int i, int j)	//求子串
{
	//从i开始长度为j的字符串
	SqString str;
	int k;
	str.length = 0;
	if (i <= 0 || i > s.length || j<0 || i + j - 1>s.length)
		return str;					//参数不正确时返回空串
	for (k = i - 1; k < i + j - 1; k++)  		//将s.data[i..i+j]复制到str
		str.data[k - i + 1] = s.data[k];
	str.length = j;
	return str;
}
SqString Concat(SqString s, SqString t)	//串连接
{
	SqString str;
	int i;
	str.length = s.length + t.length;
	for (i = 0; i < s.length; i++)	//将s.data[0..s.length-1]复制到str
		str.data[i] = s.data[i];
	for (i = 0; i < t.length; i++)	//将t.data[0..t.length-1]复制到str
		str.data[s.length + i] = t.data[i];
	return str;
}
SqString Replace(SqString S, SqString T, SqString R)
{
	if (S.length == 0 || T.length == 0) return S;
	
	//初始化空字符串
	SqString res;
	char str[] = { 0 };
	StrAssign(res, str);
	
	int index = 0;
	int over = 0;//用于记录已经处理的字符串的数量
	while ((index = KMPIndex1(SubStr(S, over + 1, S.length - over), T)) != -1)
	{
		//复制匹配之前的字符串
		SqString pre = SubStr(S, over + 1, index);
		StrCopy(res, Concat(res, pre));
		
		//复制替换串、
		StrCopy(res, Concat(res, R));
		
		over = over + index + T.length;
		
	}
	SqString nex = SubStr(S, over + 1, S.length - over);
	StrCopy(res, Concat(res, nex));
	
	return res;
	
	
}

void DispStr(SqString s)	//输出串s
{
	int i;
	if (s.length > 0)
	{
		
		for (i = 0; i < s.length; i++)
			printf("%c", s.data[i]);
		printf("\n");
	}
}

int main()
{
	printf("编写算法实现串的置换操作Replace( S, T, R), 即将串S中所有与串T相等的子串置换为串R\n");
	char str1[MaxSize] = "abbbb";
	char str2[MaxSize] = "ab";
	char str3[MaxSize] = "a";
	
	
	
	SqString S, T, R;
	StrAssign(S, str1);
	StrAssign(T, str2);
	StrAssign(R, str3);
	DispStr(S);
	DispStr(T);
	DispStr(R);
	
	
	SqString res = Replace(S, T, R);
	DispStr(res);
	
	return 0;
}
